/**
 * 最长递增子序列
 */
function sequence(arr) {
  const len = arr.length;
  const result = [0]
  const p = Array.from({ length: len }).fill(0)
  let start;
  let end;
  let middle;
  let resultLastIndex
  for (let i = 0; i < len; i++) {
    let arrI = arr[i]
    if (arrI !== 0){
      resultLastIndex = result[result.length - 1]
      if (arr[resultLastIndex] < arrI) {
        // 记录索引
        result.push(i)
        p[i] = resultLastIndex // 当前放到末尾的要记住他前面的那个人是谁
        continue
      }
      // 这里我们需要通过二分查找，在结果集中找到比当前值大的，用当前值的索引将其替换掉
      start = 0
      end = result.length - 1
      while (start < end) {
        middle = ((start + end) / 2) | 0

        if (arr[result[middle]] < arrI) {
          start = middle + 1
        }else{
          end = middle
        }
      }
      if (arr[result[start]] > arrI) {
        result[start] = i
        p[i] = result[end - 1]
      }
    }
  }
  // 通过标记索引的方式，最终通过最后一项将结果还原 (回溯 )
  let i = result.length
  const last = result[i - 1]
  while (i-- > 0) {
    result[i] = last
    last = p[last]
  }
  return result
}
// 我们可以通过 标记索引的方式，最终通过最后一项将结果还原 (回溯 )